10 typedef long long int int64
;
12 #define forsn(i, s, n) for (int64 i = (s); i < (n); i++)
13 #define forn(i, n) forsn (i, 0, n)
14 #define forall(x, s) for (typeof((s).begin()) x = (s).begin(); x != (s).end(); x++)
16 typedef vector
<int64
> vint
;
17 typedef vector
<vint
> vvint
;
21 int64 capacidad_enlace
;
22 vvint grafo
; // listas de adyacencia
23 vvint costo
; // matriz
24 vvint flujo
; // matriz
26 #define agregar(u, v, c) { \
27 grafo[u].push_back(v); \
29 grafo[v].push_back(u); \
33 #define capacidad(v, w) (((v) == 0 || (w) == 0) ? capacidad_eje0 : capacidad_enlace)
35 void print_grafo_residual() {
36 cout
<< "---------------" << endl
;
39 forall (vecino
, grafo
[v
]) {
42 cout
<< " costo = " << costo
[v
][*vecino
];
43 cout
<< " flujo = " << flujo
[v
][*vecino
] << " / " << capacidad(v
, *vecino
);
50 #define INF 0x7fffffff
51 #define No_hay_camino -1
52 #define signo(x) ((x) < 0 ? -1 : 1)
53 int64
caumento(vint
& camino
) {
54 // buscar el camino de aumento de costo minimo usando Bellman-Ford
61 // para cada arista del grafo residual
63 forn (v
, n
) forall (vecino
, grafo
[v
]) {
64 const int64 w
= *vecino
;
65 if (capacidad(v
, w
) - flujo
[v
][w
] <= 0) continue;
66 if (dist
[v
] == INF
) continue;
67 int64 ndist
= dist
[v
] + signo(flujo
[v
][w
]) * costo
[v
][w
];
68 if (ndist
< dist
[w
]) {
78 int64 costo_camino
= 0;
81 camino
.push_back(actual
);
82 int64 anterior
= ant
[actual
];
83 if (anterior
== -1) break;
84 costo_camino
+= signo(flujo
[anterior
][actual
]) * costo
[anterior
][actual
];
95 int64 flujo_total
= 0;
96 int64 costo_total
= 0;
97 while (flujo_total
< capacidad_eje0
) {
98 //print_grafo_residual();
100 int64 costo_camino
= caumento(camino_aumento
);
101 if (costo_camino
== No_hay_camino
) return No_hay_camino
;
102 // saturar el camino de aumento
105 forn (i
, camino_aumento
.size() - 1) {
106 const int64 v
= camino_aumento
[i
+ 1], w
= camino_aumento
[i
];
107 if (flujo
[v
][w
] < 0) {
108 mn
= min(mn
, -flujo
[v
][w
]);
110 mn
= min(mn
, capacidad(v
, w
) - flujo
[v
][w
]);
113 forn (i
, camino_aumento
.size() - 1) {
114 const int64 v
= camino_aumento
[i
+ 1], w
= camino_aumento
[i
];
118 if (mn
== 0) return No_hay_camino
;
120 costo_total
+= costo_camino
* mn
;
128 while (cin
>> n
>> m
) {
130 grafo
= vvint(n
, vint());
131 costo
= vvint(n
, vint(n
, 0));
132 flujo
= vvint(n
, vint(n
, 0));
137 cin
>> v1
>> v2
>> c
;
140 cin
>> capacidad_eje0
>> capacidad_enlace
;
141 int64 r
= resolver();
142 if (r
== No_hay_camino
) {
143 cout
<< "Impossible." << endl
;